Programmable logic devices (PLDs) are a class of integrated circuits which can be programmed by a user after they have been fabricated so as to emulate various logic functions. Logic designers typically use PLDs to implement control logic in electronic systems, because they are relatively easy to program and can be reprogrammed when necessary to change their logic. This makes their use in an electronic system's design phase less costly than the custom hardwired or "application specific" integrated circuits (ASICs).
One major class of PLDs has a set of input pins, a programmable AND plane connected to the input pins, an OR plane connected to outputs of the AND plane and a set of output pins connected to outputs of the OR plane. The AND plane provides a matrix of programmable connections where each column connects to an input pin and each row forms an output of the AND plane, called a product term line, which connects to the OR plane. The OR plane may be programmable, such that each product term line is connectable to columns leading to different output pins, in which case the PLD is called a programmable logic array (PLA). Alternatively, the OR plane may be fixed, such that each product term line is assigned to a particular output pin, in which case the PLD is called a programmable array logic (PAL) device.
The PLDs just described contain two levels of logic (AND and OR) and are capable of implementing logic functions that are representable in "sum of products" form. A sum of products form of a logic function is essentially a set of product terms for each output of the function. Such a logic function is represented in a PLD by programmed connections in the AND plane and OR plane. Each product term line has a programmable input connection in the AND plane to each input pin and produces a single output value representing the logical AND or "product" of the connected inputs. Usually both the original input pin value and its complement are available for connection to a product term line. Each output has a programmable product term connection in the OR plane and produces an output value representing the logical OR or "sum" of the connected product terms.
Recently, PLDs with more complex architectures have been developed. Such architectures use two or more functional blocks, each structured like the two-level PLDs described above, which are connected together to produce the final output or outputs. Connection of functional blocks may be done in a number of ways. One connection scheme uses the outputs of the functional blocks as inputs to another functional block or blocks, again structured like a simple two-level PLD. However, because an input assignment must propagate through two or more PLD functional blocks before the correct output pattern can be obtained, the propagation delay of this scheme is usually at least twice that of a single two level PLD. Another connection scheme combines outputs from two or more functional blocks in a logic expander. The logic expander is usually just a product term array and possibly followed by an inverter array which provides the necessary logical connection with less propagation delay than a PLD functional block. A third connection scheme uses a programmable interconnect matrix to logically AND inputs to or outputs from the functional blocks.
PLDs of any of the above described architectures are electronically configured, mapped or "programmed" to implement a specific logic function. A logic function in a PLD device takes a set of input pins and for each possible input assignment value produces an output pattern on the set of output pins. Usually there are a plurality of output pins and the function is a multiple output function. A single output function is a special logic function requiring only one output pin. Logic functions need not necessarily be connected to input and output pins. They may refer to the values of internal registers, and so in speaking of pins, it will be understood that internal registers are equivalents. The type of logic functions which can be implemented on a PLD described above is that which can be represented in "sum-of-products" form. The sum-of-products form of a function is essentially a set of product terms, where product terms are formed by the logical AND of one or more inputs. Such a function is easily implemented in a simple two-level PLD by connecting selected columns representing inputs or their complements in the AND plane with selected rows, i.e. product term lines, to produce product terms and connecting selected rows representing these product terms in the OR plane with selected columns to form the outputs.
It is standard practice for logic designers using two-level logic PLDs to use logic minimization steps to more efficiently program those PLDs. Logic minimization takes advantage of the realization that many different sum-of-products forms may exist for the same function, and that one particular form may be selected so as to minimize the number of required product terms. If the PLD allows for programmable inversion of the outputs, the inverse of the desired function may require fewer product terms than the function itself. In the case of PLAs and other PLDs that allow sharing of all or some product terms, a multiple output function with common product terms may be more efficiently programmed by taking advantage of this feature. Thus, these techniques allow users to pack more logic onto a given PLD.
With regard to the efficient programming of the more complex three-level logic PLDs, problems are manifest in areas such as the breaking up of a logic function into a plurality of subfunctions that can be programmed into separate output cells or functional blocks, what to do when a particular subfunction has too many input variables or product terms, or both, to fit into a single functional block, and how to make best use of the available third level of logic. One approach merely applies the logic minimization steps used for two-level logic PLDs to the subfunctions to better pack those subfunctions into the functional blocks, but does not address the situation where one or more of the subfunctions do not fit, even after minimization. The bulk of the research on multilevel logic synthesis has focused ASIC design, not in PLD functional block assignments.
Accordingly, an object of the present invention is to provide a process for programming a PLD having multiple functional blocks connected by a third level of logic, such as an interconnect matrix, which does not introduce significant propagation delays, which can handle logic having input or product term requirements that exceed the capacity of any one functional block, and which can program larger functions into the PLD.